package week06

// 300. 最长递增子序列
// https://leetcode-cn.com/problems/longest-increasing-subsequence/

func lengthOfLIS(nums []int) int {
	var f = make([]int, len(nums))
	// 以nums[i]为结尾，最长递增子序列
	// f[i] = i之前所有“小于nums[i]的数结尾的子序列”的最长长度+1
	for i, num := range nums {
		f[i] = 1
		for j := 0; j < i; j++ {
			if num > nums[j] {
				f[i] = max(f[i], f[j] + 1)
			}
		}
	}
	var ans = 0
	for _, n := range f {
		ans = max(ans, n)
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}